/*************************************************************************
	> File Name: 001.RBTree.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 五  2/19 11:11:00 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>

#define RED 0
#define BLACK 1
#define DOUBLE_BLACK 2

typedef struct Node {
    int key;
    int color;
    struct Node *lchild, *rchild;
} Node;

Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void initNIL() {
    NIL->key = 0;
    NIL->color = BLACK;
    NIL->lchild  = NIL->rchild = NIL;
    return ;
}

Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key;
    p->color = RED;
    p->lchild = p->rchild = NIL;
    return p;
}

Node *left_rotate(Node *root) {
    Node *temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    return temp;
}

Node *right_rotate(Node *root) {
    Node *temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    return temp;
}

int has_red_child(Node *root) {
    return root->lchild->color == RED || root->rchild->color == RED;
}

Node *_insert_maintain(Node *root) {
    if (!has_red_child(root)) return root;    
    int flag = 0;
    if (root->lchild->color == RED && has_red_child(root->lchild)) flag = 1;
    if (root->rchild->color == RED && has_red_child(root->rchild)) flag = 2;
    if (flag == 0) return root;
    
    if (root->lchild->color == RED && root->rchild->color == RED) {
        root->color = RED;
        root->lchild->color = root->rchild->color = BLACK;
        return root;
    }

    if (flag == 1) {
        if (root->lchild->rchild->color == RED) {
            root->lchild = left_rotate(root->lchild);
        }
        root = right_rotate(root);
    } else {
        if (root->rchild->lchild->color == RED) {
            root->rchild = right_rotate(root->rchild);
        }
        root = left_rotate(root);
    }
    root->color = RED;
    root->lchild->color = root->rchild->color = BLACK;
    return root;
}

Node *_insert(Node *root, int key) {
    if (root == NIL) return getNewNode(key);
    if (key == root->key) return root;
    if (key < root->key) root->lchild = _insert(root->lchild, key);
    else root->rchild = _insert(root->rchild, key);
    return _insert_maintain(root);
}

Node *insert(Node *root, int key) {
    root = _insert(root, key);
    root->color = BLACK;
    return root;
}

Node *_erase_maintain(Node *root) {
    if (root->lchild->color != DOUBLE_BLACK && root->rchild->color != DOUBLE_BLACK) return root;
    if (has_red_child(root)) {
        int flag = 0;
        root->color = RED;
        if (root->lchild->color == RED) {
            root = right_rotate(root);
            flag = 1;
        } else {
            root = left_rotate(root);
            flag = 2;
        }
        root->color = BLACK;
        if (flag == 1) root->rchild = _erase_maintain(root->rchild);
        else root->lchild = _erase_maintain(root->lchild);
        return root;
    }
    if ((root->lchild->color == DOUBLE_BLACK && !has_red_child(root->rchild)) || (root->rchild->color == DOUBLE_BLACK && !has_red_child(root->lchild))) {
        root->lchild->color -= BLACK;
        root->rchild->color -= BLACK;
        root->color += BLACK;
        return root;
    }
    if (root->lchild->color == DOUBLE_BLACK) {
        root->lchild->color = BLACK;
        if (root->rchild->rchild->color != RED) {
            root->rchild->color = RED;
            root->rchild = right_rotate(root->rchild);
            root->rchild->color = BLACK;
        }
        root = left_rotate(root);
        root->color = root->lchild->color;
    } else {
        root->rchild->color = BLACK;
        if (root->lchild->lchild->color != RED) {
            root->lchild->color = RED;
            root->lchild = left_rotate(root->lchild);
            root->lchild->color = BLACK;
        }
        root = right_rotate(root);
        root->color = root->rchild->color;
    }
    root->lchild->color = root->rchild->color = BLACK;
    return root;
}

Node *predecessor(Node *root) {
    Node *temp = root->lchild;
    while (temp->rchild != NIL) temp = temp->rchild;
    return temp;
}

Node *_erase(Node *root, int key) {
    if (root == NIL) return NIL;
    if (key < root->key) root->lchild = _erase(root->lchild, key);
    else if (key > root->key) root->rchild = _erase(root->rchild, key);
    else {
        if (root->lchild == NIL || root->rchild == NIL) {
            Node *temp = root->lchild != NIL ? root->lchild : root->rchild;
            temp->color += root->color;
            free(root);
            return temp;
        } else {
            Node *temp = predecessor(root);
            root->key = temp->key;
            root->lchild = _erase(root->lchild, temp->key);
        }
    }
    return _erase_maintain(root);
}


Node *erase(Node *root, int key) {
    root = _erase(root, key);
    root->color = BLACK;
    return root;
}

void clear(Node *root) {
    if (root == NIL) return ;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return ;
}

void print(Node *root) {
    //printf("(%s|%d, %d, %d)\n", root->color ? "Black" : "Red", root->key, root->lchild->key, root->rchild->key);
    printf("%d %d %d %d\n", root->key, root->color, root->lchild->key, root->rchild->key);
    return ;
}

void output(Node *root) {
    if (root == NIL) return ;
    output(root->lchild);
    print(root);
    output(root->rchild);
    return ;
}

int main() {
    int op, key;
    Node *root = NIL;
    while (~scanf("%d%d", &op, &key)) {
        switch (op) {
            case 1: root = insert(root, key); break;
            case 2: root = erase(root, key); break;
            case 3: output(root); break;
        }
    }

    return 0;
}
